package test230531;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/31 0:26
 * 174. 地下城游戏
 * https://leetcode.cn/problems/dungeon-game/
 */
public class Solution01 {

    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        // dp[i][j] 表示以 i j 位置为起点到达终点需要的最小健康值
        int[][] dp = new int[m + 1][n + 1];
        // 状态量初始化
        for (int i = 0; i <= m; ++i) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= n; ++i) {
            dp[m][i] = Integer.MAX_VALUE;
        }
        dp[m - 1][n] = dp[m][n - 1] = 1; // 无论怎样, 在终点解救公主后到达下一个位置的健康值至少为1
        // 动态规划过程
        // dp[i][j] + 当前位置需要的消耗或者获得的血包 >= 下一位置所需要的最小能力值
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(dp[i][j], 1); // 防止 dp[i][j] 原本是一个很大的数, 保证在该位置需要至少有1个健康值
            }
        }
        return dp[0][0];
    }
}
